package labuladong;

import java.util.Arrays;

public class LengthOfLIS {

    public static void main(String[] args) {

        int[] nums = new int[]{1,4,3,4,2};
        System.out.println(lengthOfLIS(nums));
    }

//    private static Integer lengthOfLIS(int[] nums) {
//        int[] dp = new int[nums.length];
//        Arrays.fill(dp,1)   ;
//        for(int i=0;i<nums.length;i++){
//            for(int j=0;j<i;j++){
//                if(nums[i]>nums[j]){
//                    dp[i]=Math.max(dp[i],dp[j]+1);
//                }
//            }
//        }
//        int res = 0;
//        for (int i = 0; i < dp.length; i++) {
//            res = Math.max(res, dp[i]);
//        }
//        return res;
//    }

    public static int lengthOfLIS(int[] nums) {
        int[] top = new int[nums.length];
        // 牌堆数初始化为 0
        int piles = 0;
        for (int i = 0; i < nums.length; i++) {
            // 要处理的扑克牌
            int poker = nums[i];

            /***** 搜索左侧边界的二分查找 *****/
            int left = 0, right = piles;
            while (left < right) {
                int mid = (left + right) / 2;
                if (top[mid] > poker) {
                    right = mid;
                } else if (top[mid] < poker) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }
            /*********************************/

            // 没找到合适的牌堆，新建一堆
            if (left == piles) piles++;
            // 把这张牌放到牌堆顶
            top[left] = poker;
        }
        // 牌堆数就是 LIS 长度
        return piles;
    }

}
